#include "algo.h"
#include <stdlib.h>
#include <string.h>

static void
makeTreeAux(const Graph *graph, Graph * tree, int s,bool * available){
  vector<int> neighbours = graph->getNeighbours(s);
  int i = 0;
  for(;i<neighbours.size();i++){
    if(available[neighbours[i]])
      {
	available[neighbours[i]] = false;
	tree->addEdge(s,neighbours[i]);
	makeTreeAux(graph,tree,neighbours[i],available);
      }
  }
}



static Graph * makeTree(const Graph *graph, Graph * tree){
  bool * available = (bool*)malloc(sizeof(bool) * graph->getNbVertex() );
  memset(available,true,graph->getNbVertex());
  for (int i = 0; i<graph->getNbVertex(); i++)
      tree->addVertex();
  available[0]=false;
  makeTreeAux(graph, tree, 0,available);
  return tree;
  
}




//renvoie la liste des sommets couvrants
vector<int>
ApprocheArbre(const Graph *graph) {
  Graph * tree = makeTree(graph,new Graph());
  cout << tree->toString() << endl;

  return optitree(tree);
  
}


